package src.leetcode.hot.mid_0148;

import java.util.Random;


public class sortList {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(0);
        ListNode node2 = new ListNode(4, node1);
        ListNode node3 = new ListNode(3, node2);
        ListNode node4 = new ListNode(5, node3);
        ListNode node5 = new ListNode(-1, node4);
        ListNode node6 = new ListNode(6, node5);
        Solution.getRandomNode(node6, node5);
        new Solution().sortList(node5);
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        // TODO
        if (head == null || head.next == null) return head;
        ListNode dummp = new ListNode(0, head);
        sortList(dummp, null);
        return dummp.next;
    }

    public void sortList(ListNode dummp, ListNode tail) {
        if (dummp == null || dummp.next == null || dummp.next.next == null) return ;
        if (dummp == tail || dummp.next == tail || dummp.next.next == tail) return ;

        ListNode node = getRandomNode(dummp, tail);
        ListNode mid = partition(dummp, tail, node);
        sortList(dummp, mid.next);
        sortList(mid, tail);
    }

    static ListNode getRandomNode(ListNode dummp, ListNode tail) {
        ListNode node = dummp;
        int count = 0;
        while (node.next != null && node.next != tail) {
            node = node.next;
            count++;
        }
        if (count == 0) return dummp.next;
        Random ran = new Random();
        int index = ran.nextInt(0, count);
        node = dummp.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    public ListNode partition(ListNode dummp, ListNode tail, ListNode index) {
        if (dummp.next == tail) return tail;
        ListNode dummp1 = new ListNode(0);
        ListNode dummp2 = new ListNode(0);
        ListNode node1 = dummp1;
        ListNode node2 = dummp2;
        ListNode node = dummp;
        while (node.next != null && node.next != tail) {
            if (node.next.val >= index.val) {
                node2.next = node.next;
                node2 = node2.next;
            } else {
                node1.next = node.next;
                node1 = node1.next;
            }
            node = node.next;
        }
        node1.next = dummp2.next;
        node2.next = tail;
        dummp.next = dummp1.next;
        if (node1.next != null) return node1;
        return dummp;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}